package cxydmmszl.chapter04.t058;

import java.util.Scanner;

/**
 * <li style="color: red;">Prob</li>
 * 换钱的最少货币数
 * <li style="color: red;">Desc</li>
 * 给定数组 arr，arr 中所有的值都为正整数且不重复。每个值代表一种面值的货币，
 * 每种面值的货币可以使用任意张，再给定一个 aim，代表要找的钱数，求组成 aim 的最少货币数。<br/><br/>
 * 输入描述：<br/>
 * 输入包括两行，第一行两个整数 n（0<=n<=1000）代表数组长度和 aim（0<=aim<=5000），
 * 第二行 n 个不重复的正整数，代表 arr（1<=arr[i]<=10^9）。<br/><br/>
 * 输出描述：<br/>
 * 输出一个整数，表示组成 aim 的最小货币数，无解时输出-1。
 * <li style="color: red;">Link</li> CD12
 *
 * @author habitplus
 * @since 2021-08-31 17:29
 */
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int aim = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        int ans = minCoins2(arr, aim);
        System.out.println(ans);
    }

    public static int minCoins2(int[] arr, int aim) {
        if (arr == null || arr.length < 1 || aim < 0) {
            return -1;
        }

        int n = arr.length;
        int[][] dp = new int[n + 1][aim + 1];

        // 设置最后一排的值，除 dp[n][0]=0 外，其他都是 -1
        for (int i = 1; i <= aim; i++) {
            dp[n][i] = -1;
        }

        for (int i = n - 1; i >= 0; i--) { // 从底往上计算一行
            for (int rest = 0; rest <= aim; rest++) { // 每一行都是从左往右
                // 初始时先设置 dp[i][rest] 的值无效
                //下面的值如果有效，先设置成下面的值
                dp[i][rest] = dp[i+1][rest];

                // 如果左边的位置不越界且有效
                if (rest - arr[i] >= 0 && dp[i][rest - arr[i]] != -1) {
                    if (dp[i][rest] == -1) {
                        dp[i][rest] = dp[i][rest - arr[i]] + 1;
                    } else {
                        dp[i][rest] = Math.min(dp[i][rest], dp[i][rest - arr[i]] + 1);
                    }
                }
            }
        }

        return dp[0][aim];
    }
}
